﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProgrammingIsMyPassion.Coding
{
    public class SortRotateFind
    {
        public void Rotate(ref int[] array)
        {
            int rotatedX = array[0];
            for (int i = 0; i < array.Length - 1; i++)
            {
                array[i] = array[i + 1];
            }
            array[array.Length - 1] = rotatedX;

        }

        public int Min(int[] array)
        {
            int start = 0;
            int end = array.Length - 1;
            return AllocateMinIndex(array, start, end);
        }
        public int AllocateMinIndex(int[] array, int start, int end)
        {
            //input array is sorted and rotated in a queue order(dequeue -> enqueue) 
            int result = 0;
            if (start >= end)
                return array[start];
            //if the array is sorted. the previous item must be > current item.
            //assum the array is like a circle
            if (array[end] > array[start])
                return array[start];

            if (end - start == 1)
            {
                if (array[start] > array[end])
                    return array[end];
                else
                    return array[start];
            }
            int mid = start + (end - start) / 2;
            if (mid - 1 >= start && array[mid - 1] > array[mid])
                return array[mid];

            if (array[mid] > array[start] && array[mid] > array[end])
            {
                if (array[end] < array[start])
                    result = AllocateMinIndex(array, mid, end);
                else
                    result = AllocateMinIndex(array, start, mid);
            }
            else if (array[mid] < array[start] && array[mid] < array[end])
            {
                if (array[mid - 1] < array[mid])
                    result = AllocateMinIndex(array, start, mid);
            }
            //else if (array[mid] > array[start] && array[mid] < array[end])
            //{
            //    //array is sorted
            //    return array[start];
            //}
            return result;
        }
    }
}
